var trace = function(x) {
	document.write('<pre>' + html_escape(sprintf.apply(this, arguments)) + '</pre>');
};


var Stream = function(str) {
	this.load(str);
};
Stream.prototype = {
	EOF: -1,
	load: function(str) {
		this.source = str;
		this.length = this.source.length;
		this.reset();
	},
	eof: function() {
		return this.char === this.EOF;
	},
	reset: function() {
		this.pos = 0;
	},
	getch: function() {
		if (this.pos >= this.length)
			return this.char = this.EOF;
		return this.char = this.source[this.pos++];
	}
};

var last_rule_id = 1;

var lex_rule = function(str, f) {
	var out = [];
	var i, max = str.length;
	for (i = 0; i < max; ++i)
		out[i] = {};
	//var action = function() { f(str) };
	var action = f;
	//action.toString = function() { return '[' + str + ']' };
	out[out.length] = { action: action };
	for (i = 0, max = out.length - 1; i < max; ++i)
		out[i][str[i]] = out[i + 1];
	return out[0];
};


var lex_merge = function(r1, r2) {
	//r2 = objoin({}, r2);
	
	if (r2.action && !r1.action) {
		r1.action = r2.action;
	}
	
	// XXX
	//if (r2.group)
	//	r1.group = r2.group;

	for (var i in r2) {
		if (i.length > 1 && i != 'any') continue;
		if (!r1[i]) {
			//r1[i] = objoin({}, r2[i]);
			r1[i] = r2[i];
			continue;
		}
		lex_merge(r1[i], r2[i]);
	}
	
	if (r2.any) {
		for (var i in r1) {
			if (i.length > 1 && i != 'any') continue;
			lex_merge(r1[i], r2.any);
		}
	}
	
	
	

	if (r2.default_action) {
		x = {};
		if (r1.default_action)
			x.d = r1.default_action;
		y = { d: r2.default_action };
		obcat(x, y);
		r1.default_action = x.d;
	}
	
	return r1;
};


var lex_run = function(initial, input) {
	var s, state = initial;
	var c;
	//console.dir(state);
	var i = 0, max = input.length;
	yytext = '';
	var d;
	var last_accepting_pos = 0, last_accepting_state = initial;
	var action;
	var x;
	var yytext_pos = 0;
	
	var cnt = 0;
	while (true) {
		if (cnt++ > 100) { alert('hang up'); return; }
		
		if (i >= max) break;
		//trace(input[i]);
		
		state = initial;
		var gg = [], g0 = 0, g;
		while (s = state[input[i]] || state.any) {
			g = s.gr || 0;
			
			if (state.action) {
				last_accepting_state = state;
				last_accepting_pos = i;
			}
			++i;
			state = s;
			if (i >= max)
				break;
		}
		//alert(dump(state));
		if (!state.action) {
			state = last_accepting_state;
			i = last_accepting_pos;
		}
		yytext = input.substr(yytext_pos, i - yytext_pos);
		yytext_pos = i;
		
		if (state.action) {
			x = state.action();
			trace('action: ' + x);
		}
		
	}
};


var add_range = function(assoc, start, end) {
	for (var i = start.charCodeAt(0), max = end.charCodeAt(0); i <= max; ++i)
		assoc[String.fromCharCode(i)] = 1;
	return assoc;
};

var parse_range = function(stream) {
	var c, c0;
	var assoc = {};

stream_loop:	
	while (true) {
		c = stream.getch();
		if (stream.eof())
			break;
		switch (c) {
			case ']':
				break stream_loop;
			default:
				assoc[c] = 1;
				break;
			case '.':
				assoc.any = 1;
				break;
			case '-':
				if (c0 === undefined)
					assoc[c] = 1;
				else {
					c = stream.getch();
					add_range(assoc, c0, c);
				}
				break;
			case '\\':
				c = stream.getch();
				switch (c) {
					case 'w':
						add_range(assoc, 'a', 'z');
						add_range(assoc, 'A', 'Z');
						assoc['_'] = 1;
						//add_range(assoc, 'A', 'Z');
						break;
					case 'd': add_range(assoc, '0', '9'); break;
					case 's': assoc[' '] = assoc['\t'] = 1; break;
					case 't': assoc['\t'] = 1; break;
					case 'n': assoc['\n'] = 1; break;
					case 'r': assoc['\r'] = 1; break;
					default: assoc[c] = 1; break;
				}
				break;
		}
		c0 = c;
	}
	var out = [];
	for (var i in assoc)
		if (assoc[i] == 1)
			out[out.length] = i;
	out.sort();
	return out;
	
	//throw "']' expected in regexp";
};


var parse_re = function(source) {
	var rec = function(stream, result) {
		var c = stream.getch();
		switch (c) {
			case stream.EOF:
				return result;
			default:
				result.push(['C', c]);
				return rec(stream, result);
			case '\\':
				c = stream.getch();
				switch (c) {
					case 'w': result.push(['R', parse_range(new Stream('a-zA-Z_'))]); break;
					case 'd': result.push(['R', parse_range(new Stream('0-9'))]); break;
					case 's': result.push(['R', parse_range(new Stream(' \t'))]); break;
					case 'r': result.push(['C', '\r']); break;
					case 'n': result.push(['C', '\n']); break;
					default:  result.push(['C', c]); break;
				}
				return rec(stream, result);
			case '|':
				var x = rec(stream, []);
				return [['|', result, x]];
			case '[':
				var r = parse_range(stream);
				result.push(['R', r]);
				return rec(stream, result);
			case '(':
				var x = rec(stream, []);
				result.push(['G', x]);
				return rec(stream, result);
			case ')':
				//return result.length == 1 ? result[0] : result;
				return result;
			case '?':
				result.push(['?', [result.pop()]]);
				return rec(stream, result);
			case '+':
				result.push(['+', [result.pop()]]);
				return rec(stream, result);
			case '*':
				result.push(['*', [result.pop()]]);
				return rec(stream, result);
			case '.':
				result.push(['.']);
				return rec(stream, result);
		}
	};
	if (source.constructor === RegExp)
		source = source.source;
	//alert(source);
	var stream = new Stream(source);
	var result = rec(stream, []);
	//result.source = source;
	return result;
};


var re_to_string = function(re) {
	var out = [];
	var hd;
	
	for (var i = 0, max = re.length; i < max; ++i) {
		hd = re[i];
		
		switch (hd[0]) {
			case '.':
				out[out.length] = '.';
				break;
				
			case 'C':
				out[out.length] = re_escape(hd[1]);
				break;

			case 'G':
				out[out.length] = '(';
				out[out.length] = re_to_string(hd[1]);
				out[out.length] = ')';
				break;

			case 'R':
				var cc = hd[1], a0, a1, a2, a3;
				//alert(cc);
				if (cc.length == 1) {
					switch (cc[0]) {
						case 'any': out[out.length] = '.'; break;
						default: out[out.length] = re_escape(cc[0]); break;
					}
					break;
				}
				
				out[out.length] = '[';
				for (var j = 0, jmax = cc.length; j < jmax; ++j) {
					if (cc[j] == 'any') { out[out.length] = '.'; continue; }
					if (j + 3 < jmax) {
						a0 = cc[j+0].charCodeAt(0);
						a1 = cc[j+1].charCodeAt(0);
						a2 = cc[j+2].charCodeAt(0);
						a3 = cc[j+3].charCodeAt(0);
						if (a1 == a0 + 1 && a2 == a1 + 1 && a3 == a2 + 1) {
							out[out.length] = re_escape(cc[j]) + '-';
							for (var n = a1; j + 1 < jmax && n == cc[j + 1].charCodeAt(0); ++j, ++n);
						}
					}
					out[out.length] = re_escape(cc[j]);
				}
				out[out.length] = ']';
				//alert(out);
				break;

			case '+':
				var x = hd[1];
				out[out.length] = re_to_string(x) + '+';
				break;

			case '*':
				var x = hd[1];
				out[out.length] = re_to_string(x) + '*';
				break;
				
			case '?':
				var x = hd[1];
				out[out.length] = re_to_string(x) + '?';
				break;

			case '|':
				var x = hd[1];
				//alert(x);
				var y = hd[2];
				out[out.length] = re_to_string(x) + '|' + re_to_string(y);
				break;
		}
	}
	return out.join('');
};


var lex_re = function(re, action) {
	if (re.constructor === RegExp)
		re = parse_re(re);
	
	trace(dump(re));
	
	var depth = 0;
	var max_group = 0;

	var rec = function(re, accept, g) {
		if (!re.length)
			return accept;			
		var hd = re[0];
		var tl = re.slice(1);
		var n = rec(tl, accept, g);

		//if (group === undefined)
		//	group = 0;
		
		while (hd.length == 1 && is_array(hd[0]))
			hd = hd[0];

		switch (hd[0]) {
			case 'R':
				//alert(hd[1]);
				var x = {};
				var cc = hd[1];
				for (var i = 0, max = cc.length; i < max; ++i)
					x[cc[i]] = n;
				return x;
				
			case 'G':
				//group = max_group + 1;
				//++group;
				var m = {};
				objoin(m, n);
				var a = rec(hd[1], m, ++max_group);
				
				
				/*
				for (var i in a) {
					if (i.length != 1 && i != 'any') continue;
					if (!a[i].group)
						a[i].group = [];
					a[i].group.push(group);
				}
				*/
				return a;
				
			case 'C':
				var x = {};
				//x[hd[1]] = n;
				
				var y = {};
				y.gr = g;
				objoin(y, n);
				x[hd[1]] = y;
				
				return x;

			case '.':
				var x = {};
				x.any = n;
				return x;

			case '|':
				var a = rec(hd[1], n);
				var b = rec(hd[2], n);
				lex_merge(a, b);
				return a;

			case '+':
				var a = rec(hd[1], n);
				lex_merge(n, a);
				return a;

			case '*':
				var a = rec(hd[1], n);
				lex_merge(n, a);
				return n;

			case '?':
				var a = rec(hd[1], n);
				lex_merge(a, n);
				return a;
			}
	};
	//var accept = { action: "RE: " + (re.source || re)};
	action.toString = function(){ return re_to_string(re) };
	var accept = { action: action };
	return rec(re, accept, 0);
};





